package LiKou;

import java.util.*;

public class Problem1436 {
    public static void main(String[] args) {

    }
    public static String destCity(List<List<String>> paths) {
        if(paths.size()==0){
            return "";
        }
        if(paths.size()==1){
            return paths.get(0).get(1);
        }
        String result="";
        Set<String> end=new HashSet<>();
        Set<String> start=new HashSet<>();
        int len=paths.size();
        for(int i=0;i<len;i++){
            end.add(paths.get(i).get(1));
            start.add(paths.get(i).get(0));
        }
        for(String i:start){
            if(end.contains(i)){
                end.remove(i);
            }
        }
        for(String i : end){
            result = i;
        }
        return result;
    }
    public static String destCity2(List<List<String>> paths) {
        if(paths.size()==0){
            return "";
        }
        if(paths.size()==1){
            return paths.get(0).get(1);
        }
        String result="";
        Map<String,String> map=new HashMap<>();
        for(int i=0;i<paths.size();i++){
            map.put(paths.get(i).get(0),paths.get(i).get(1));
        }
        for(String s:map.values()){
            if(!map.keySet().contains(s)){
                result=s;
            }
        }
        return result;
    }
    public static String destCity3(List<List<String>> paths) {
        Set<String> citiesA = new HashSet<String>();
        for (List<String> path : paths) {
            citiesA.add(path.get(0));
        }
        for (List<String> path : paths) {
            if (!citiesA.contains(path.get(1))) {
                return path.get(1);
            }
        }
        return "";
    }
}
